---
title: "7、积木画"
created: 2025-11-28
tags:
  - 算法
---

# 7、积木画

## 题目 [积木画](https://www.lanqiao.cn/paper/3822/problem/2110/)

![[image-28274c51.png]]

## 思路分析

![[image-cdc2df0c.png]]

画图找了一下规律 发现并没有什么公式的性质在

倒是体会到了一点dp的味道

然后尝试了一下好像真的可以

画图找规律 画了又擦 擦了又画 花了一个多小时吧 考试真心不建议做……

![[image-88bdf276.png]]

大概找到了个规律 所有的情况都会从前面已有的积木拼接而成 而1→2是会产生一个新拼法的（宽度增加 横着放变成一种可能） 2→3会增加两种新拼法（宽度增加
让放体积为3的积木成为可能 要拼满 3的积木需要成对出现 占据2\*2的方格）3→4会增加两种新拼法(两长边衔接 宽为4） 然后后面应该就不会出现什么新的方法了
都可以从前面的积木组合而来 然后组合后的积木可以忽略不用它进行下一步组合 因为它一定可以被组合前的几种积木的组合替换

所以 大概就是 转变成了 （因为高固定 所以只有宽会变） 在宽度N的限制下 选以下这6种物品

![[image-daf22e5c.png]]

每个物品可以选择多次 然后体积（宽度）不太一样 第一个宽1 第二个宽2 第三第四宽3

完全背包问题吗

但是怎么解决 1,2 2,1不是同一种的问题

……

找了一下别人的写法 也差不多分析到了这里

但是我方向跟他走岔了

![[image-e5e16afe.png]]

![[image-8b732a14.png]]

## 代码实现

```cpp
#include <stdio.h>

#define mod 1000000007

int main()

{

    long long  n = 0;

    long long a, b, c, d;

    a = 1，b = 1, c = 2;

    scanf("%lld", &n);

    for (int i = 3; i <= n; i++)

    {

        d = (c * 2 + a) % mod;

        a = b;

        b = c;

        c = d;

    }

    printf("%lld", d);

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[6、统计子矩阵|6、统计子矩阵]] 🏠 [[00-刷题理模型]] ➡️ [[8、扫雷|8、扫雷]]